package _动态规划系列._打家劫舍;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/2 12:40
 * <p>
 * 功能描述:
 */
public class Summary_0337 {

    /**
     * 3
     * / \
     * 4   5
     * / \   \
     * 1   3   1
     */
    Map<TreeNode,Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        if (root == null)
            return 0;

        if (memo.containsKey(root))
            return memo.get(root);

        //抢，然后去下下家
        int rob_it = root.val
                + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
                + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));

        //不抢，然后去下家
        int not_rob = rob(root.left) + rob(root.right);

        int res = Math.max(rob_it, not_rob);
        memo.put(root,res);
        return res;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}